package fibonacci_problem

// 暴力方法
func GetFibonacci(n int) int {
	if n < 0 {
		return 0
	}
	if n == 1 || n == 2 {
		return 1
	}
	return GetFibonacci(n-1) + GetFibonacci(n-2)
}


// 动态规划
func GetFibonacciDp(n int) int {
	if n < 0 {return 0}
	dp := make([]int, n)
	dp[0] = 1
	dp[1] = 1
	for i:=2; i<n; i++ {
		dp[i] = dp[i-2] + dp[i-1]
	}
	return dp[n-1]
}

// 动态规划
func GetFibonacciDp1(n int) int {
	if n < 0 {return 0}
	if n == 1 || n ==2 {
		return 1
	}
	res := 1
	pre := 1
	tem := 0
	for i:=3; i<=n; i++ {
		tem = res
		res = res + pre
		pre = tem
	}
	return res
}

// 线性代数矩阵方式，最优解，时间复杂度 logN
func GetFibonacciMatrix(n int) int {
	if n < 0 {return 0}
	// f(n) = f(n-1) + f(n-2)
	// |f(n),f(n-1)| = |f(1),f(2)| * |base| ^ n-2
	// 算法复杂度取决于 算base的n-2次方的最优解
	// 求指数最优的方式是采用二分的方式将指数变成二进制数进行乘法运算
	base := [][]int{
		[]int{1, 1},
		[]int{1, 0},
	}
	baseNR2 := powMatrix(base, n-2)
	return baseNR2[0][0] + baseNR2[1][0]
}

func powMatrix(base [][]int, n int) [][]int {
	size := len(base[0])
	res := make([][]int, size)
	for i:=0; i<size; i++ {
		res[i] = make([]int, size)
		res[i][i] = 1
	}
	for ; n != 0; n >>= 1 {
		if (n & 1) != 0 {
			res = multiMatrix(res, base)
		}
		base = multiMatrix(base, base)
	}
	return res
}

func multiMatrix(matrix1 [][]int, matrix2 [][]int) [][]int {
	size := len(matrix1[0])
	res := make([][]int, size)
	for i:=0; i<size; i++ {
		res[i] = make([]int, size)
	}

	for i:=0; i<size; i++ {
		for j:=0; j<size; j++ {
			var curAns int
			for k:=0; k<size; k++ {
				curAns += matrix1[i][k] * matrix2[k][j]
			}
			res[i][j] = curAns
		}
	}
	return res
}
